package gold.digger;

import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (null == root) {
            return res;
        }

        Stack<TreeNode> stPrev = new Stack<>();
        Stack<TreeNode> stNext = new Stack<>();
        stPrev.push(root);
        boolean isNormalVisit = true;
        while (!stPrev.isEmpty() || !stNext.isEmpty()) {
            Stack<TreeNode> st = stPrev.empty() ? stNext : stPrev;
            Stack<TreeNode> stEmp = stPrev.empty() ? stPrev : stNext;
            List<Integer> curRes = new ArrayList<>();
            while (!st.isEmpty()) {
                TreeNode cur = st.pop();
                curRes.add(cur.val);
                if (isNormalVisit) {
                    if (null != cur.left) {
                        stEmp.push(cur.left);
                    }
                    if (null != cur.right) {
                        stEmp.push(cur.right);
                    }
                } else {
                    if (null != cur.right) {
                        stEmp.push(cur.right);
                    }
                    if (null != cur.left) {
                        stEmp.push(cur.left);
                    }
                }
            }
            isNormalVisit = !isNormalVisit;
            res.add(curRes);
        }

        return res;
    }

    public static void main(String[] args) {
        LC103 an = new LC103();
        /**
         Given binary tree [3,9,20,null,null,15,7],
         */
        System.out.println(an.zigzagLevelOrder(TreeNode.createTree("3,9,20,null,null,15,7")));

    }
}
